Typical packet-switched data communications systems adhere to some sort of multi-layered communications protocol. These protocol layers include a network layer, whose functions control the transportation of data from source to destination node. Network layer functions are implemented at distributed nodes of the network.
Although the services provided by the network layer may vary in accordance with different switching techniques and sublayer requirements, one common service provided by the network layer is routing. Thus, the network layer includes a routing algorithm that is responsible for deciding on which output link a message packet should be transmitted. Of course, the primary objective of the routing algorithm is that the packet reach its destination. Several other objectives are important, such as minimizing packet transit times, avoiding congestion and deadlocks, and maximizing network throughput. It also desirable that the algorithm be as simple, robust, stable, and fair to users, as possible.
Today's data communications networks use a number of different routing algorithms. An example of a routing algorithm is a broadcast algorithm, in which a message is delivered to all possible destinations.
A routing algorithm that is suitable for one type of message is not always the best algorithm for another topology, especially in SONET networks. For example, broadcast algorithms are suitable for certain topologies, such as tree topologies, but not for other topologies, such as ring topologies. A characteristic of routing algorithms, especially those used for ring topologies, is that more than one route may be selected and used for a given message. In complicated topologies, such as the dual ring topology, duplication of a message along multiple routes could result in substantial network loading.
An alternative to routing algorithms is selective routing, where a network is manually provisioned and routing decisions are made by accessing a database of predetermined paths. Using this approach to routing, all routes between network elements are fixed until the network is reprovisioned, instead of being the result of an algorithm that makes real time routing decisions based on current conditions. If the provisioning is carefully done, some of the problems associated with routing algorithms may be avoided, but the provisioning process tends to be tedious.
Routing algorithms make use of routing protocols to identify the facilities and network elements that provide a path. A routing protocol in common use today is known as the ES-IS routing exchange protocol. This protocol defines all routing nodes as either an end system (ES) or an intermediate system (IS) or both. Under the ES-IS protocol, each routing node is provided with a ES-IS database, which stores the identity of other nodes with whom it has direct connection and whether those neighbors are capable of receiving or routing data. The ES-IS protocol is part of the ISO 9542 standard. In one implementation of the ES-IS protocol, if a node with a message to send has a direct connection to the destination node (an ES), it sends the message to that node; otherwise it sends the message to all network elements that can route (ISs). Although this approach to ES-IS routing avoids manual provisioning, its IS aspects are not efficient in networks having complicated topologies.
Another routing protocol, which is currently under development, is the IS-IS protocol. Routing methods based on this protocol will be able to efficiently handle routing between multiple ISs and will be useful in network having complicated topologies. However, the IS-IS protocol has not yet been fully developed.
Routing decisions can be implemented on interoffice transmission systems as well as on single local area networks. For interoffice communications, a recently proposed protocol for networks using fiber optic links is known as SONET (synchronous optical network). The SONET standards are set out in American National Standards (ANSI) T1.105 and T1.106. A similar standard is the SDH (synchronous digital hierarchy) standard of the International Consultative Committee for Telephone and Telegraph (CCITT). In general, SONET calls for a synchronous fiber optic based data transmission system that supports both synchronous and asynchronous tributaries.
The administration for SONET networks is accomplished by a centralized control system known as TMN (telecommunications maintenance network). Eventually, TMN administration provide routing methods based on the IS-IS routing protocol. However, at this time, routing for SONET networks is accomplished by selective routing, which as stated above, requires manual provisioning of all elements within a network. The provisioning is made difficult by the fact that SONET networks may have a general topology comprised of network applications, each having their own different topology. Development of a suitable routing algorithm has also been hindered by this general topology.